首页 CRYPTO

# [NPUCTF2020]Mersenne twister

链接

from hashlib import *
from itertools import *
from binascii import hexlify , unhexlify
from flag import flag ,seed
assert len(flag) == 26
assert flag[:7] == 'npuctf{'
assert flag[-1] == '}'
XOR = lambda s1 ,s2 : bytes([x1 ^ x2 for x1 ,x2 in zip(s1 , s2)])
class mt73991:
   def __init__(self , seed):
       self.state = [seed] + [0] * 232
       self.flag = 0
       self.srand()
       self.generate()
   def srand(self):
       for i in range(232):
           self.state[i+1] = 1812433253 * (self.state[i] ^ (self.state[i] >> 27)) - i
           self.state[i+1] &= 0xffffffff
   def generate(self):
       for i in range(233):
           y = (self.state[i] & 0x80000000) | (self.state[(i+1)%233] & 0x7fffffff)
           temp = y >> 1
           temp ^= self.state[(i + 130) % 233]
           if y & 1:
               temp ^= 0x9908f23f
           self.state[i] = temp
   def getramdanbits(self):
       if self.flag == 233:
           self.generate()
           self.flag = 0
       bits = self.Next(self.state[self.flag]).to_bytes(4 , 'big')
       self.flag += 1
       return bits
       
   def Next(self , tmp):
       tmp ^= (tmp >> 11)
       tmp ^= (tmp << 7) & 0x9ddf4680
       tmp ^= (tmp << 15) & 0xefc65400
       tmp ^= (tmp >> 18) & 0x34adf670
       return tmp
def encrypt(key , plain):
   tmp = md5(plain).digest()
   return hexlify(XOR(tmp , key))
if __name__ == "__main__":
   flag = flag.encode()
   random = mt73991(seed)
   f = open('./cipher.txt' , 'wb')
   for i in flag:
       key = b''.join([random.getramdanbits() for _ in range(4)])
       cipher = encrypt(key , chr(i).encode())
       f.write(cipher)
 
 
 
#cef4876036ee8b55aa59bca043725bf350a5e491debdef7ef7d63e9609a288ca1e2c82a7fe566bd8709e73c8d495ea504a486ed11189faf8e6fb35617e47d2d1ad5e4783e96afeaae9f7104ec477fb39fe4ec619bf58289709e15c4449f03fc51cba918cd0ebfdc12376b41e7815406482733b3b200826b6c78d86563edaea94dccf459a4291517a4b8367d7b4a53aeecd7e0accf661bfc726f5ba62e1c0e04100108ad32e7d5711f780185cba5cf31d328bee84066be4ab9582cf9d4bfe3c6f96a7732e1c37d800c90fd46277147f0a26c149dcd5eeb0f2df0c075627bc220be5eefdd67186056ac28c21e155a7f247664aaecdb498134de274df10114d1f06f84dd21820f150d69c9439d909dec0f5ccfeab61b62db2ea91d31bc8163ff16c7f458006bd5ac4a5f5bfae2770b23ccfb7195b76aa0a9aa146831667a7b9fe08c19e691afadccb3ca5169ef3fabaa3dad47d536e89ed4cee6f788bc969c3ad3137850ebfc46a73af2b0c036c3da4b4a16506f499445c604dd73eeb846a52f881515a3ad0ab448b4f9ed3e0ab1fffac60b223dde6450ba6198e90e14de107aaf2
MT19937 类型的
我们可以知道 flag 以 'npuctf' 开头
那么可以求出前几个随机数
这道题需要求的是 seed
那么只要知道第一个随机数就可以
然后可以逆一下 next ()
之前存的脚本
import string
from binascii import hexlify
from hashlib import md5
from Crypto.Util.number import *
# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp
def extract_number(tmp):
    tmp ^= (tmp >> 11)
    tmp ^= (tmp << 7) & 0x9ddf4680
    tmp ^= (tmp << 15) & 0xefc65400
    tmp ^= (tmp >> 18) & 0x34adf670
    return tmp
def recover(y):
    y = inverse_right_mask(y,18,0x34adf670)
    y = inverse_left_mask(y,15,0xefc65400)
    y = inverse_left_mask(y,7,0x9ddf4680)
    y = inverse_right(y,11)
    return y
c='cef4876036ee8b55aa59bca043725bf350a5e491debdef7ef7d63e9609a288ca1e2c82a7fe566bd8709e73c8d495ea504a486ed11189faf8e6fb35617e47d2d1ad5e4783e96afeaae9f7104ec477fb39fe4ec619bf58289709e15c4449f03fc51cba918cd0ebfdc12376b41e7815406482733b3b200826b6c78d86563edaea94dccf459a4291517a4b8367d7b4a53aeecd7e0accf661bfc726f5ba62e1c0e04100108ad32e7d5711f780185cba5cf31d328bee84066be4ab9582cf9d4bfe3c6f96a7732e1c37d800c90fd46277147f0a26c149dcd5eeb0f2df0c075627bc220be5eefdd67186056ac28c21e155a7f247664aaecdb498134de274df10114d1f06f84dd21820f150d69c9439d909dec0f5ccfeab61b62db2ea91d31bc8163ff16c7f458006bd5ac4a5f5bfae2770b23ccfb7195b76aa0a9aa146831667a7b9fe08c19e691afadccb3ca5169ef3fabaa3dad47d536e89ed4cee6f788bc969c3ad3137850ebfc46a73af2b0c036c3da4b4a16506f499445c604dd73eeb846a52f881515a3ad0ab448b4f9ed3e0ab1fffac60b223dde6450ba6198e90e14de107aaf2'
p='n'.encode()
tmp=md5(p).hexdigest()
XOR = lambda s1 ,s2 : bytes([x1 ^ x2 for x1 ,x2 in zip(s1 , s2)])
m1=eval('0x'+tmp[:8])^eval('0x'+c[:8])
key=recover(m1)
print(key)
然后再求 seed
爆破 seed，python 跑起来很慢。。。用 c++ 跑
更新一下
知道 flag 最后一位‘}’ 就知道 state [103] 可以求出 state [104]
就可以逆回去
from gmpy2 import invert
def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908f23f
    state = cur
    tmp = state[1]^state[0]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<=1
    # recover highest bit
    state= tmp & low
    return state
def invert_right(res,shift):
    tmp = res
    for i in range(32//shift):
        res = tmp^res>>shift
    return res&0xFFFFFFFF
def recover(last):
    n = 1<<32
    inv = invert(1812433253,n)
    for i in range(104,0,-1):
        last = ((last+i-1)*inv)%n
        last = invert_right(last,27)
    return last
s=[778501557,1167644902]
s228=backtrace(s)
print(bin(s228))
seed=(recover(s228))
print(seed)
得到 seed 直接可以求解
seed=1668245885
class mt73991:
    def __init__(self, seed):
        self.state = [seed] + [0] * 232
        self.flag = 0
        self.srand()
        self.generate()
    def srand(self):
        for i in range(232):
            self.state[i + 1] = 1812433253 * (self.state[i] ^ (self.state[i] >> 27)) - i
            self.state[i + 1] &= 0xffffffff
    def generate(self):
        for i in range(233):
            y = (self.state[i] & 0x80000000) | (self.state[(i + 1) % 233] & 0x7fffffff)
            temp = y >> 1
            temp ^= self.state[(i + 130) % 233]
            if y & 1:
                temp ^= 0x9908f23f
            self.state[i] = temp
    def getramdanbits(self):
        if self.flag == 233:
            self.generate()
            self.flag = 0
        bits = self.Next(self.state[self.flag]).to_bytes(4, 'big')
        self.flag += 1
        return bits
    def Next(self, tmp):
        tmp ^= (tmp >> 11)
        tmp ^= (tmp << 7) & 0x9ddf4680
        tmp ^= (tmp << 15) & 0xefc65400
        tmp ^= (tmp >> 18) & 0x34adf670
        return tmp
c='cef4876036ee8b55aa59bca043725bf350a5e491debdef7ef7d63e9609a288ca1e2c82a7fe566bd8709e73c8d495ea504a486ed11189faf8e6fb35617e47d2d1ad5e4783e96afeaae9f7104ec477fb39fe4ec619bf58289709e15c4449f03fc51cba918cd0ebfdc12376b41e7815406482733b3b200826b6c78d86563edaea94dccf459a4291517a4b8367d7b4a53aeecd7e0accf661bfc726f5ba62e1c0e04100108ad32e7d5711f780185cba5cf31d328bee84066be4ab9582cf9d4bfe3c6f96a7732e1c37d800c90fd46277147f0a26c149dcd5eeb0f2df0c075627bc220be5eefdd67186056ac28c21e155a7f247664aaecdb498134de274df10114d1f06f84dd21820f150d69c9439d909dec0f5ccfeab61b62db2ea91d31bc8163ff16c7f458006bd5ac4a5f5bfae2770b23ccfb7195b76aa0a9aa146831667a7b9fe08c19e691afadccb3ca5169ef3fabaa3dad47d536e89ed4cee6f788bc969c3ad3137850ebfc46a73af2b0c036c3da4b4a16506f499445c604dd73eeb846a52f881515a3ad0ab448b4f9ed3e0ab1fffac60b223dde6450ba6198e90e14de107aaf2'
table=string.printable
random=mt73991(seed)
for i in range(0,len(c),32):
    tmp=c[i:i+32]
    key=b''.join([random.getramdanbits() for _ in range(4)])
    key=bytes_to_long(key)
    md=hex(eval('0x'+tmp)^key)[2:].zfill(32)
    for j in table:
        if(md5(j.encode()).hexdigest()==md):
            print(j,end='')
            break
主要是字节，hex，字符串转换有点混乱。。